#include <stdio.h>
#include <stdbool.h>

#define DIRECTINSERTSORT    0
#define SEMIINSERTSORT      0
#define SHELLINSERTSORT     0
#define BUBBLECOMPARESORT   1

#if DIRECTINSERTSORT
void DirectInsertSort(int *arr,int length)
{
    for(int i = 1;i < length;i++)
    {
        int temp = arr[i];
        int j = 0;
        for(j = i - 1;j >= 0;j--)
        {
            if(temp < arr[j])
            {
                arr[j + 1] = arr[j];
            }
            else
            {
                break;
            }
        }
        arr[j+1] = temp;
    }
    printf("this is DirectInsertSort\n");
}
#endif//DIRECTINSERTSORT

#if SEMIINSERTSORT
void SemiInsertSort(int *arr,int length)
{
    int low=0,mid=0,high=0;
    for(int i = 1;i < length;i++)
    {
        int temp = arr[i];
        if(temp < arr[i-1])
        {
            low = 0;
            high = i - 1;
            while(low <= high)
            {
                mid = (low + high) / 2;
                if(arr[mid] > temp)
                {
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }
            for(int j = i - 1;j >= low;j--)
            {
                arr[j+1] = arr[j];
            }
            arr[low] = temp;
        }
    }
    printf("this is SemiInsertSort\n");
}
#endif//SEMIINSERTSORT

#if SHELLINSERTSORT
void ShellInsertSort(int *arr,int length)
{
    int gap = length;
    while(gap > 1)
    {
        gap = gap / 3 + 1;
        for(int i = gap; i < length;i++)
        {
            int temp = arr[i];
            int end = i - gap;
            while(end >= 0)
            {
                if(temp < arr[end])
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = temp;
        }
    }
    printf("this is ShellInsertSort\n");
}
#endif//SHELLINSERTSORT

#if BUBBLECOMPARESORT
void BubbleCompareSort(int *arr,int length)
{
    bool isEntry = false;
    for(int i = 0;i < length - 1;i++)
    {
        isEntry = false;
        for(int j = 0;j < length - 1 - i;j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                isEntry = true;
            }
        }
        if (!isEntry) break;
        
    }
    printf("this is BubbleCompareSort\n");
}
#endif//BUBBLECOMPARESORT

int main()
{
    int arr[] = {99,88,77,71,67,56,45,44,43,33,25,20,15,12,10,6,2,1};
    int length = sizeof(arr) / sizeof(arr[0]);

#if DIRECTINSERTSORT
    DirectInsertSort(arr,length);
#endif//DIRECTINSERTSORT

#if SEMIINSERTSORT
    SemiInsertSort(arr,length);
#endif//SEMIINSERTSORT

#if SHELLINSERTSORT
    ShellInsertSort(arr,length);
#endif//SHELLINSERTSORT

#if BUBBLECOMPARESORT
    BubbleCompareSort(arr,length);
#endif//BUBBLECOMPARESORT

    for(int i = 0;i < length;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");

    return 0;
}
